package leetcode.D100.T5;

class Solution {
    // 解法一：动态规划
    public String longestPalindrome(String s) {
        boolean[][] dp = new boolean[s.length()][s.length()];
        for(int i=0; i<dp.length; ++i) {
            dp[i][i] = true;
            if(i > 0 && s.charAt(i) == s.charAt(i-1)) {
                dp[i-1][i] = true;
            }
        }
        for(int step=2; step <s.length(); ++step) {
            for(int i=0; i<s.length(); ++i) {
                int j = i + step;
                if(j >= s.length()) {
                    break;
                }
                if(dp[i+1][j-1] && s.charAt(i) == s.charAt(j)) {
                    dp[i][j] = true;
                }
            }
        }
        for(int step=s.length()-1; step>=0; --step) {
            for(int i=0; i<s.length(); ++i) {
                int j = i + step;
                if(j >= s.length()) {
                    break;
                }
                if(dp[i][j]) {
                    return s.substring(i, j+1);
                }
            }
        }
        return s;
    }
}
